package com.origin.niuke.dynamic;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/5/23 23:12
 * 最长公共子序列(二)
 * 算法：动态规划
 */
public class NC92 {

    StringBuilder ans = new StringBuilder();
    public String LCS (String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        if (len1 == 0 || len2 == 0) return "-1";
        int[][] dp = new int[len1 + 1][len2 + 1];
        int[][] b = new int[len1 + 1][len2 + 1];
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    b[i][j] = 1;
                } else {
                    if (dp[i][j - 1] > dp[i - 1][j]) {
                        dp[i][j] = dp[i][j - 1];
                        b[i][j] = 2;
                    } else {
                        dp[i][j] = dp[i - 1][j];
                        b[i][j] = 3;
                    }
                }
            }
        }
        recursion(len1, len2, b, s2);
        if (ans.length() == 0) return "-1";
        return ans.toString();
    }
    void recursion(int i, int j, int[][] b, String s2) {
        if (i == 0 || j == 0) return;
        if (b[i][j] == 1) {
            recursion(i - 1, j - 1, b, s2);
            ans.append(s2.charAt(j - 1));
        } else if (b[i][j] == 2) recursion(i, j - 1, b, s2);
        else recursion(i - 1, j, b, s2);
    }

}
